// 加油站

package Leetcode;

class solution_134 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        int[] weight = new int[length];
        int sum = 0;
        for (int i = 0; i < length; i++) {
            weight[i] = gas[i] - cost[i];
            sum += weight[i];
        }
        if (sum < 0)
            return -1;
        for (int i = 0; i < length; i++) {
            // 如果第一站油量就小于0
            if (weight[i] < 0)
                continue;
            else {
                int value = 0; // 当前油量
                int j = i; // 起始位置
                for (int k = 0; k < length; k++) {
                    value += weight[j];
                    if (value < 0)
                        break;
                    j = (j + 1) % length;
                }
                if (j == i)
                    return j;
            }
        }
        return -1;
    }
}

class Solution134 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        int start = 0;
        while (start < length) {
            int currentGas = 0;
            int i = 0; // 从start点遍历数组，如果成立必须要遍历length
            for (; i < length; i++) {
                int j = (start + i) % length;
                currentGas += gas[j] - cost[j];
                if (currentGas < 0)
                    break;
            }
            // 如果遍历完全则返回
            if (i == length)
                return start;
            else {
                // 从第一个不可达点开始重新遍历
                start += i + 1;
            }
        }
        return -1;
    }
}